from typing import List

class Solution:
    def resultGrid(self, image: List[List[int]], threshold: int) -> List[List[int]]:
        
        def in_area(x, y, xs, ys):
            return xs<=x<=xs+2 and ys<=y<=ys+2
        
        def is_valid(x, y, xs, ys, th):
            for xi,yi in [(x-1,y),(x+1,y),(x,y-1),(x,y+1)]:
                if in_area(xi, yi, xs, ys):
                    if abs(image[x][y] - image[xi][yi]) <= th:
                        continue
                    else:
                        return False
            return True
                
            
        m = len(image)
        n = len(image[0])
        res = [[[] for j in range(n)] for i in range(m)]
        for i in range(m-2):
            for j in range(n-2):
                if is_valid(i+1,j,i,j,threshold) and is_valid(i,j+1,i,j,threshold) and is_valid(i+2,j+1,i,j,threshold) and is_valid(i+1,j+2,i,j,threshold):
                    locations = list(zip(range(i, i+3),range(j, j+3)))
                    avg = sum([image[x][y] for x,y in locations]) // 9
                    for x,y in locations:
                        (res[x][y]).append(avg)
        
        for i in range(m):
            for j in range(n):
                res[i][j] = sum(res[i][j])//len(res[i][j]) if res[i][j] else image[i][j]
        
        return res

if __name__ == '__main__':
    s = Solution()
    print(s.resultGrid(
        [[5,6,7,10],[8,9,10,10],[11,12,13,10]],
        3
    ))